Source: Wikipedia
Quiz 1 has been graded, and your results are posted on Gradescope
This week's assignments
A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution. Digital signatures provide part of the solution, but the main benefits are lost if a trusted third party is still required to prevent double-spending.
– Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System
By the end of today's lecture, you will learn:
Bitcoin was invented in 2009 by an anonymous party (or parties) holding the pseudonym Satoshi Nakamato.
Bitcoin is a digital currency that does not require a single, trusted banking authority to manage everybody's transactions and bank balances. Instead, everyone on the Internet that uses the Bitcoin software collectively keeps track of how many Bitcoins each party holds at any moment in time.
In the physical world, when Bob receives a check from Alice, he may be suspicious that Alice is trying to deceive him. He needs to be able to verify the following three properties.
For a digital monetary system: digital signatures satisfy property #1, and a blockchain can satisfy the other two objectives.
A blockchain is a public ledger. It is:
Source: Wikipedia
There are three types of data structures to consider within Bitcoin:
A transaction is a request to transfer money, just like a physical check from a sender to a receiver. The sender must sign the transaction to prove to the world that it consents to the money transfer, and the sender must point to the prior transaction(s) in which she received the money that she is trying to send now. Also, transactions are irrevocable.
[Source: mempool.space, at block 828285]
[Image source: Nakamoto whitepaper]
There are three types of participants within Bitcoin.
A light client only needs to hold one or more secret keys for a digital signature scheme.
A node additionally stores the entire state of the blockchain.
A miner additionally tries to write new blocks on the blockchain. (We will discuss miners in more detail today.)
Bitcoin needs miners; without them no new blocks would be created. So the Bitcoin system incentivizes people to create new blocks by providing two financial rewards:
You get to create new coins out of thin air. Specifically, you get 6.25 Bitcoins, which is worth about $260,000 at current exchange rates. (This is the only way that new Bitcoins get introduced into circulation. In Bitcoin terminology, this is called a coinbase transaction.)
You receive the transaction fees that people set aside for you within their transactions. The average Bitcoin transaction fee is currently around $6.50 per transaction.
The creation (or non-creation) of blocks needs to be done in such a way as to protect against 3 types of attacks.
Censorship: The miner can refuse to post certain transactions. This would break our goal of allowing anyone to append new information to the end of the book.
Inconsistency: The miner can send different states of the blockchain to different nodes. This would break our goal of having a global ledger that anyone can read.
Double spending: The miner could go back in time and rewrite an earlier block. This would break our goal that the ledger is append-only. Consider the following example:
[Image source: Bitcoin wiki]
Mining a block earns you a lot of money! Seems like it might be nice to have the job of being a miner.
Question. Suppose that you have a job opening and there are millions of applicants. You can't hire everyone, and in fact you cannot even interview everyone. What would you do?
In fact, mining might be too nice of a job. If mining a block wins so much money, what's to stop the next person from overwriting the block so they get the mining rewards instead?
Modern computers are incredibly fast. They can transmit, write, and overwrite data in the blink of an eye.
But in a financial system like Bitcoin, speed is not the most important goal. Instead, we want to make sure that everyone has a consistent view of the blockchain ledger that they agree upon.
Cryptocurrencies like Bitcoin have been carefully designed to ensure that censorship, inconsistency, and double spending attacks are practically infeasible to perform.
(Note: Bitcoin's protections against these 3 attacks are actually related, but for the purposes of this class, we will treat them separately.)
Within Bitcoin, "practically infeasible" does not always mean "energy of the sun" levels of difficult. Instead, the goal is to ensure that the attacks are onerous enough to perform that:
Question. How would you design a financial payment system to protect against censorship, inconsistency, and double-spending?
One possible option is to find a single person who the whole world trusts, and ask that person to be the sole miner in the scheme.
Sadly, we do not have such fully-trusted people. If we somehow found such a person, we might ask them to run everything for us, not just the banks. In political terms, this corresponds to a (benevolent?) dictatorship.
To extend the political analogy further, over the centuries humankind has designed democratic social structures in which we:
These political systems are often less efficient and nimble than a dictatorship might be, but they are more stable as a result.
Cryptocurrencies abide by these principles too! Let's see how.
Let's see how Bitcoin thwarts these attacks, one at a time. For now, let's just assume that the miners all promise never to conduct a double-spend attack. (We'll fix this trust issue later.)
Bitcoin includes two components to thwart censorship:
There is a connected network of Bitcoin nodes that gossip or broadcast any transaction they hear. This way, any sender can get their transactions heard by any node and miner who happen to be connected to the network right now.
We will say more about broadcast protocols in future lectures. For now let's assume that this part works perfectly. To see how it works, take a look at the animation at time 1:51 to 2:02 in the YouTube video below.
There is a randomized election system (or in other words, a lottery) to choose the next miner. It doesn't matter (much) who wins the election; the important part is that the nodes have agreement on who has won.
The upshot here is: each individual miner can still censor your transaction if they want. Nevertheless, as long as at least one miner is honest, then your transaction will eventually get put into a block.
This is an example of an anytrust assumption; we will see more examples later in the semester.
The miner inserts into the newly-created block their winning lottery ticket -- which is formally called a nonce, for reasons we will see soon.
Other miners and nodes will only consider a block to be valid if it includes a winning nonce.
Just like with the earlier political analogy: we have designed a cryptocurrency that is more stable, but at the expense of speed. Whereas you might assume that an Internet-based money scheme would be fast, instead this system is purposely slow. Within Bitcoin,
In computer science terms: the throughput of this monetary system is low.
This strategy also solves the problem of inconsistency, which was the fear that nodes might see different blockchains.
(Recall that we are assuming for the moment that miners will never go back and try to rewrite history.)
Even with this simplifying assumption in place, one concern is that two miners might win the lottery at (almost) the same time. If this happens
They will produce different blocks, called B and B2 in the picture below. These blocks might have the same transactions or they may have different transactions. Either way, they contain different nonces, and each block creator has awarded all mining rewards and fees to themselves.
But: both blocks will point to the same previous block, called A in the picture below.
In Bitcoin terminology, this is called a fork of the blockchain.
[Image source: Mango Research]
We can overcome this forking issue by using the peer-to-peer network to broadcast these blocks as well. Then we can impose a rule that all honest nodes should follow:
Always choose the largest* blockchain. As a tiebreaker, choose the chain that you heard first.
In Bitcoin terminology, each block contains a counter called its block height.
(*Note: we will make one small tweak to this rule in a few minutes.)
[Image source: Mango Research]
Once again, we have resolved an attack at the expense of speed. Let's look at the above picture in the following scenario: block A already exists, and then two miners win the lottery at nearly the same time and post blocks B and B2.
Suppose also your transaction occurred in block B but not in block B2.
In computer science terms: the latency of any individual transaction is high.
The final -- and most insidious -- attack that we have to prevent is the double spend.
The threat here is that a malicious buyer Mallory does the following.
[Image source: Bitcoin wiki]
We will also solve this problem by intentionally imposing friction into the cryptocurrency. Specifically, we haven't discussed yet how miners win the election and get the right to create a new block.
Assume that there are more honest miners than dishonest miners. Our goal is to choose an election method that is fairly likely to elect an honest miner.
[Image source: Nakamoto whitepaper]
Here's how it works. Every miner collects all of the transactions from the peer-to-peer network, and forms a block. Then:
nonce value however it wants. (It can choose this at random, or make a counter, or anything it wants.)nonce.0 bits, then the miner has won the election and quickly posts the result to the peer-to-peer network. Otherwise, it goes back to step #1 to try again.Note that in each calculation of the hash function, the transactions in the block can remain the same (or they can change, if new transactions arrive and the miner wishes to add them to the block).
What's important is that the nonce changes for each execution of the hash function. The Bitcoin miners keep calculating
for many, many different nonces. The miner wins the election if this hash digest $y$ is a small enough number, i.e., it begins with enough 0 bits.
Currently, the Bitcoin miners collectively perform about $556 \cdot 10^{18}$ hashes per second.
This corresponds to $334 \cdot 10^{21}$ hashes every 10 minutes. The difficulty level of Bitcoin is currently set to require this many hash computations in expectation, in order to produce a winning nonce.
[Image source: blockchain.info]
This effort by the miners is called a proof of work. Only after performing this work can a miner post a block.
This is a lot of computational work! By means of comparison,
So you would need around 100 billion graphics cards to keep up with the hash rate of the entire Bitcoin network!
Note: actual Bitcoin miners do not use general-purpose computer processors and graphics cards. Instead, they use special hardware that is designed solely to perform SHA-256 as quickly and cheaply as possible.
To see the proof of work property in action, let's look at a recent block created on the Bitcoin blockchain.
# Every block references the hash of the previous block
# Fetching block 828285 that we explored last time
import requests
from binascii import unhexlify
# getting the block hash of block 828285
block_hash = requests.get('https://mempool.space/api/block-height/828285').text
# get block metadata
response = requests.get('https://mempool.space/api/block/' + block_hash)
block_hash = response.json()['previousblockhash']
print(block_hash)
000000000000000000021cc74c4da673f53f0cad485844e4bcdd4e42514ba420
The block hash starts with a lot of 0 hex characters! (19 of them, to be precise.) This is very unlikely to occur by chance.
Let's look at the hash digest in binary format.
print(format(int(block_hash, 16), '#0258b')[2:])
0000000000000000000000000000000000000000000000000000000000000000000000000000001000011100110001110100110001001101101001100111001111110101001111110000110010101101010010000101100001000100111001001011110011011101010011100100001001010001010010111010010000100000
This 256 bit string begins with 78 zeroes!
Question. If you choose a bitstring $x$ at random and feed it into SHA-256, what is the probability that the resulting output begins with 78 zeroes?
We can reason about this question using the random oracle property of a hash function, which states that the output "looks random."
If an adversary [Mallory] has not explicitly queried ... on some point $x$, then the value of $H(x)$ is completely random... at least as far as [Mallory] is concerned.
– Jon Katz and Yehuda Lindell, Introduction to Modern Cryptography
If every bit of the hash digest "looks" uniformly random, then this question is essentially asking about the chance of flipping a coin and it landing heads 78 times in a row.
The probability of this happening is $\frac{1}{2^{78}}$. You will need to attempt this experiment about $2^{78}$ times in order to find a hash digest like this one.
That is the proof of work game in action!
Concretely: Bitcoin relies on the following property of a hash function called puzzle friendliness.
Definition (puzzle friendliness). If we ask the miners to find an input $x$ whose SHA-256 hash digest $H(x)$ begins with $d$ zero bits in a row, then we believe there is no strategy that the miners can perform that is more effective than a guess-and-check approach. As a result, this computation is expected to take $2^d$ time.
Puzzle friendliness is a stronger guarantee than collision resistance, but a weaker guarantee than the random oracle assumption.
We have four different assumptions that we can make about a hash function:
Preimage resistance < Collision resistance < Puzzle friendliness < Random oracle.
Cryptographers assume that the SHA-2 and SHA-3 family of hash functions satisfy all of these assumptions.
Because the computational power in the world goes up over time due to Moore's Law, the difficulty of the puzzle must adjust over time.
In Bitcoin, the difficulty changes once every 2 weeks or so.
As a result, we need to make a small change to the rule that honest nodes follow:
Always choose the blockchain with the most cumulative difficulty.
In general, this typically corresponds to the blockchain with the tallest height.
Bitcoin relies on the following assumption:
The majority of the computational power used for mining (at any given time) is controlled by honest miners.
If this assumption holds, then a leader election based on proof of work (eventually) stops double-spending attacks. That's because a dishonest miner cannot keep up with the raw computing power of the honest majority.
On the other hand: if an attacker actually has the majority of the hash power, then they can solve proof of work puzzles faster than the honest miners and can therefore rewrite history!
Note that this assumption is different than the "anytrust" assumption, which was all that we needed to ensure censorship resistance.
To see why Bitcoin needs an honest majority of computing power, let's use the same forking picture as before, but change the scenario as follows:
D has been posted.B.
[Image source: Mango Research]
To do this, the miner will need to post many proofs of work in a row, very quickly. It needs to create $3 + N$ blocks faster than the real world produces $N$ blocks.
This is a Markov chain problem!
Nakamoto's whitepaper includes the following function (which I translated from C++ into Python). It calculates the probability that an attacker who controls a q fraction of the computing power of the network can execute a double-spend attack to overwrite the last z blocks in the blockchain.
# Code adapted from the Bitcoin whitepaper at https://bitcoin.org/bitcoin.pdf
from math import exp, pow
def AttackerSuccessProbability(q: float, z: int):
p = 1.0 - q
poisson_lambda = z * (q / p)
sum = 1.0
for k in range(z+1):
poisson = exp(-poisson_lambda)
for i in range(1, k+1):
poisson = poisson * poisson_lambda / i
sum = sum - poisson * (1 - pow(q / p, z - k))
return sum
q = 0.1
print("q =", q)
for z in range(10):
print("z =", z, "\t Prob =", format(AttackerSuccessProbability(q, z),"1.7f"))
print("")
q = 0.3
for z in range(0, 55, 5):
print("z =", z, "\t Prob =", format(AttackerSuccessProbability(q, z),"1.7f"))
q = 0.1 z = 0 Prob = 1.0000000 z = 1 Prob = 0.2045873 z = 2 Prob = 0.0509779 z = 3 Prob = 0.0131722 z = 4 Prob = 0.0034552 z = 5 Prob = 0.0009137 z = 6 Prob = 0.0002428 z = 7 Prob = 0.0000647 z = 8 Prob = 0.0000173 z = 9 Prob = 0.0000046 z = 0 Prob = 1.0000000 z = 5 Prob = 0.1773523 z = 10 Prob = 0.0416605 z = 15 Prob = 0.0101008 z = 20 Prob = 0.0024804 z = 25 Prob = 0.0006132 z = 30 Prob = 0.0001522 z = 35 Prob = 0.0000379 z = 40 Prob = 0.0000095 z = 45 Prob = 0.0000024 z = 50 Prob = 0.0000006
This code shows that even if a dishonest miner controls 10% of all the hash computing power on the blockchain, it will only have about a 1.3% chance of succeeding at double-spending a transaction from z = 3 blocks ago.
The attacker can increase its chance of success by buying or renting more computational power.
In response, defenders can resist this attack by waiting for more blocks to be confirmed in the public, honest chain.
Suppose there is a transaction that pays you money, but you don't trust the sender and you want to be confident that the money is "safe" and cannot be taken away from you through a double spend attack. You want to be 99.9% confident that your money is safe (i.e., that a double-spend succeeds with at most 0.1% probability).
The Nakamoto whitepaper includes the following table that shows how many blocks you need to see mined after your block, as a function of the dishonest miner's computational power.
| Adversary's computational power | # blocks required |
|---|---|
| 10% | 5 |
| 15% | 8 |
| 20% | 11 |
| 25% | 15 |
| 30% | 24 |
| 35% | 41 |
| 40% | 89 |
| 45% | 340 |
There are two important takeaways from this table:
The hash power required to execute a double-spend attack quickly becomes onerous enough to be not worth it, for all but the most expensive transactions. Even if the attacker controls even 10% of the Bitcoin network's computing power, executing a double spend attack will likely take more than one hour. By contrast, if the miner uses this hash power honestly to create new blocks, it could have earned (in expectation) tens of thousands of dollars in mining fees.
On the other hand, if the attacker controls the majority of the hash power, then your money is never safe; even transactions made years ago could eventually be double-spent. This is called a 51% attack.
Let's state that a node considers a block to be finalized if it is at least $k$ blocks deep inside of the longest chain. We'll declare a transaction to be finalized if it is part of a finalized block. (The choice of $k$ here affects the probability of an erroneous decision.)
Overall, this proof of work construction achieves the following objectives.
(Note that we have not yet provided any security guarantees to the light clients.)
In order to achieve these goals, Bitcoin is purposely designed to be:
Over the next few weeks of this course, we will explore alternative ways to satisfy the liveness and safety goals with different tradeoffs.